The present disclosure relates to autonomous computing and mobility.
Today, many autonomous computer systems rely on detection and recognition techniques for various different applications. However, for a mobile robot, the task of finding an object or person in an environment can be a challenging one. Some older solutions rely heavily on an accurate perceptual classification algorithm that guarantees an object will be found if the robot can point a sensor (e.g. a camera) at the target. Unfortunately, such classification reliability is often highly unlikely in everyday use. Even people make mistakes when recognizing objects. Given significant environmental occlusions, lighting conditions, or simply viewing the object from a difficult angle, the robot often fails to find the target and continues to aimlessly search the environment.
Searching an environment for an object (person, inanimate object, etc.) has been a task of great interest to mobile robotics for a long time, and is one that generally continues to lack an effective solution for an arbitrary environment. There have been a number of methods proposed over the years in various different domains that have attempted to solve this problem.
Search and rescue is a domain of significant interest when discussing searching for objects. Within this domain, planning-based approaches have been commonly proposed and evaluated for searching an unknown environment, making use of classic algorithmic solutions such as frontier-based search and the travelling salesman problem. One such approach is described in the work: Miroslav Kulich et al., “Single robot search for a stationary object in an unknown environment,” Robotics and Automation (ICRA), 2014 IEEE International Conference on Robotics and Automation (2014).
Another work: Nicola Basilico et al., “Defining effective exploration strategies for search and rescue applications with Multi-Criteria Decision Making,” Robotics and Automation (ICRA), 2011 IEEE International Conference on Robotics and Automation (2011), follows a related vein of work in which search is treated as a decision problem in which the navigational solutions seek to maximize a number of different search goals with varying levels of importance every time the robot is moved.
The solutions proposed by the above works, however, are designed to search an unknown environment with no prior knowledge of where the object is located—building a map of the environment while searching for people and objects. Neither of these works directly address the varying ability of the robot to observe an object in their navigational choices.
An alternative method that does address bad sensor positioning in the auditory domain is described in the work: Eric Martinson et al., “Noise Maps For Acoustically Sensitive Navigation,” Mobile Robots XVII (2004). This work proposed an approach that samples the environment repeatedly to build the map first, and then follow a gradient to detected sound sources by maximizing the signal to noise ratio in the map. Alternatively, moving away from known sound sources minimized environmental interference when listening for new auditory events. The approach, however, is limited in its application to search because it requires a lengthy sample of the environment first, and does not apply to arbitrary sensing domains where angle of observation is important.
Evidence or occupancy grids have been used by some solutions in robot guidance. This approach combines evidence together in a spatial representation or map, and uses it to guide a robot. The work: Eric Martinson et al., “Auditory Evidence Grids,” 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (2006), extended this approach in the auditory domain, incorporating directional sound measurements in an evidence grid representation to indicate probabilistically where noisy objects were most likely located based on the sum of the observations collected by the robot.
Some solutions describe guiding robots using evidence grids, such as U.S. patents: U.S. Pat. No. 8,427,472 to Moravec (Moravec) and U.S. Pat. No. 8,855,911 to Ma et al. Moravec, in particular, identifies a method in which a mobile robot can search for an object in the environment based on the evidence grid. However, there is a significant problem with using underlying evidence grid representation for search. It was designed originally for mapping obstacles in the environment and represents how likely any particular discretized location in the environment is to contain an object (e.g. an obstacle). The evidence grid does not indicate how a robot should position itself to actually detect or recognize the object. Instead, the assumption is that if the sensor is pointed at the object, then the object will be detected with some known likelihood of detection. In practice, however, robots are often unable to accurately estimate the likelihood of detection without knowing both the position and orientation of the object the robot is searching for, which is impracticable for most search applications (e.g., why would the robot be searching for the object if it already knows where it is?). To get around these difficulties with evidence grids, robot engineers attempt to resort to heuristics for navigation controllers, such as introducing random noise and forcing the robot to search the area multiple times. Such ad hoc solutions for overcoming limitations associated with using evidence grids to searching an area often leads to undesirable motion and failure to find the target object in cluttered spaces.
In contrast to the uninformed search that often defines search and rescue, a person can often pitch in to help the robot in some types of environments. This can be passive or active assistance to help a robot set search priorities. Passive assistance may, for example, use images tagged and uploaded to the Internet by people to build association graphs between different objects and/or visual features. If the robot can find a related object, it might lead to the actual target of the search. This method, of course, assumes that the environment being searched is similar to the pictures used to build the co-occurrence graph, an assumption that often proves false for a particular environment. See Puwanan Chumtong et al., “Vision-based object search in unknown human environment using object co-occurrence Graph,” Robotics and Biomimetics (ROBIO), 2011 IEEE International Conference on Robotics and Biomimetics (2011).
Some solutions use a combination of active and passive information to inform the search algorithm, such as that proposed by Mehdi Samadi et al., “Using the Web to interactively learn to find objects” AAAI'12 Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (2012), which uses returns from a search engine query to identify relative semantic associations. An example includes a “printer room” being more likely than “kitchen” when searching for paper. As with the above solution, this method, of course, assumes that the environment being searched is similar to query results, an assumption that also often proves false for a particular environment. This solution also proposes asking people directly to help with finding the object within the room, rather than continuing to search autonomously after reaching the correct vicinity, which can result in an overreliance on active information.